package org.example;

import java.util.*;

public class LL1Parser {
    Grammar grammar;
    Map<String, Set<String>> firstSets = new HashMap<>();
    Map<String, Set<String>> followSets = new HashMap<>();
    Map<String, Map<String,Production>> parsingTable = new HashMap<>();
    private List<ParsingStep> steps = new ArrayList<>(); // 存储解析步骤
    private List<String> errorMessages = new ArrayList<>(); // 存储错误信息

    public LL1Parser(Grammar grammar) {
        this.grammar = grammar;
        computeFirstSets();
        computeFollowSets();
        buildParsingTable();
    }

    // 获取解析步骤列表
    public List<ParsingStep> getSteps() {
        return steps;
    }

    // 获取错误信息列表
    public List<String> getErrorMessages() { return errorMessages; }


    /**
     * 计算FIRST集
     */
    private void computeFirstSets(){
        // 初始化FIRST集 - 为所有符号（终结符和非终结符）初始化
        for (String nonTerminal : grammar.nonTerminals) {
            firstSets.put(nonTerminal, new HashSet<>());
        }

        // 终结符的FIRST集是它自身
        for (String terminal : grammar.terminals) {
            firstSets.put(terminal, new HashSet<>());
            firstSets.get(terminal).add(terminal);
        }

        // 确保ε也有FIRST集
        firstSets.put("ε", new HashSet<>());
        firstSets.get("ε").add("ε");

        boolean changed;//FIRST集合是否有更新
        do{
            changed=false;
            for(Production production : grammar.productions){
                String left = production.left;
                List<String> right = production.right;

                boolean canBeEmpty = true;//能否推出ε
                for(String symbol : right){
                    if(grammar.terminals.contains(symbol)){//终结符
                        if(!firstSets.get(left).contains(symbol)){
                            firstSets.get(left).add(symbol);
                            changed = true;
                        }
                        canBeEmpty = false;
                        break;
                    }else {
                        //将当前非终结符的 FIRST 集合（除 ε 外）加入左部非终结符的 FIRST 集合
                        Set<String> firstOfSymbol = firstSets.get(symbol);
                        for(String s : firstOfSymbol){
                            if(!s.equals("ε") && !firstSets.get(left).contains(s)){
                                firstSets.get(left).add(s);
                                changed = true;
                            }
                        }
                        //判断是否可以继续推导后续符号
                        if(!firstOfSymbol.contains("ε")){
                            canBeEmpty = false;
                            break;
                        }
                    }

                }
                if(canBeEmpty && !firstSets.get(left).contains("ε")){
                    firstSets.get(left).add("ε");
                    changed = true;
                }
            }
        }while (changed);
    }


    /**
     * 计算FOLLOW集
     */
    private void computeFollowSets(){
        for(String nonTerminal : grammar.nonTerminals){
            followSets.put(nonTerminal,new HashSet<>());
        }
        //开始符添加$
        followSets.get(grammar.startSymbol).add("$");

        boolean changed;
        do{
            changed = false;
            for(Production production : grammar.productions){
                String left = production.left;
                List<String> right = production.right;

                for(int i=0;i<right.size();i++){
                    String current = right.get(i);
                    //处理产生式右部的非终结符
                    if(grammar.nonTerminals.contains(current)){
                        Set<String> temp = new HashSet<>();
                        boolean allEpsilon = true;

                        //计算当前非终结符后面符号的FIRST集
                        for(int j=i+1;j<right.size();j++){
                            String next = right.get(j);
                            temp.addAll(firstSets.get(next));

                            if(!firstSets.get(next).contains("ε")){
                                allEpsilon = false;
                                break;
                            }
                        }

                        //添加FIRST集到FOLLOW集
                        temp.remove("ε");
                        for(String s : temp){
                            if(!followSets.get(current).contains(s)){
                                followSets.get(current).add(s);
                                changed = true;
                            }
                        }
                        //后面的符号都能推出空串||当前是最后一个符号
                        if(allEpsilon || i==right.size()-1){
                            for(String s : followSets.get(left)){
                                if(!followSets.get(current).contains(s)){
                                    followSets.get(current).add(s);
                                    changed = true;
                                }
                            }
                        }
                    }
                }
             }
        }while(changed);
    }

    /**
     * 构建预测分析表
     */
    private void buildParsingTable(){
        for(String nonTerminal : grammar.nonTerminals){
            parsingTable.put(nonTerminal,new HashMap<>());
        }
        for(Production production : grammar.productions){
            String left = production.left;
            List<String> right = production.right;

            //计算右部符号串的FIRST集
            Set<String> firstOfRight = computeFirstOfSequence(right);

            //处理FIRST集中除ε外的终结符
            for(String terminal : firstOfRight){
                if(!terminal.equals("ε")){
                    parsingTable.get(left).put(terminal,production);
                }
            }

            //处理ε产生式的FOLLOW集
            if(firstOfRight.contains("ε")){
                for(String terminal : followSets.get(left)){
                    parsingTable.get(left).put(terminal,production);
                }
            }
        }
    }

    /**
     * 计算右部符号串的FIRST集
     * @param sequence
     * @return
     */
    private Set<String> computeFirstOfSequence(List<String> sequence){
        Set<String> result = new HashSet<>();
        boolean allEpsilon = true;

        for(String symbol : sequence){
            result.addAll(firstSets.get(symbol));
            if(!firstSets.get(symbol).contains("ε")){
                allEpsilon = false;
                break;
            }
        }
        if(allEpsilon){
            result.add("ε");
        }else {
            result.remove("ε");
        }
        return result;
    }

    public boolean parse(List<String> inputTokens) {
        List<String> tokens = new ArrayList<>(inputTokens);
        tokens.add("$");

        Stack<String> stack = new Stack<>();
        stack.push("$");
        stack.push(grammar.startSymbol);

        int index = 0;
        String lookahead = tokens.get(index);
        int stepNumber = 1;

        // 记录初始步骤
        steps.add(new ParsingStep(stepNumber++, stack.toString(),
                tokens.subList(index, tokens.size()).toString(), "初始状态"));

        boolean errorDetected = false;

        while (!stack.isEmpty()) {
            String top = stack.peek();

            // 匹配成功的情况
            if (top.equals(lookahead)) {
                // 先记录步骤，再执行栈操作
                steps.add(new ParsingStep(stepNumber++, stack.toString(),
                        tokens.subList(index, tokens.size()).toString(), "匹配 " + lookahead));
                stack.pop();
                index++;
                if (index < tokens.size()) {
                    lookahead = tokens.get(index);
                }
                continue;
            }


            // 栈顶是终结符但不匹配 - 错误
            if (grammar.terminals.contains(top)) {
                String errorMessage = "错误: 期望 " + top + " 但找到 " + lookahead +
                        "，位置: " + index + "，输入符号: " + (index < inputTokens.size() ? inputTokens.get(index) : "$");
                errorMessages.add(errorMessage);
                steps.add(new ParsingStep(stepNumber++, stack.toString(),
                        tokens.subList(index, tokens.size()).toString(), "错误: 期望 " + top + " 但找到 " + lookahead));

                // 恐慌模式恢复 - 跳过当前输入直到找到同步符号
                if (!recoverFromError(stack, lookahead, index, tokens)) {
                    return false;
                }
                continue;
            }


            // 栈顶是非终结符 - 查表选择产生式
            Production production = parsingTable.get(top).get(lookahead);
            if (production == null) {
                String errorMessage = "错误: 没有 " + top + " 在 " + lookahead + " 下的产生式" +
                        "，位置: " + index + "，输入符号: " + (index < inputTokens.size() ? inputTokens.get(index) : "$");
                errorMessages.add(errorMessage);
                steps.add(new ParsingStep(stepNumber++, stack.toString(),
                        tokens.subList(index, tokens.size()).toString(), "错误: 没有 " + top + " 在 " + lookahead + " 下的产生式"));

                // 恐慌模式恢复
                if (!recoverFromError(stack, lookahead, index, tokens)) {
                    return false;
                }
                continue;
            }

            // 先弹出栈顶，再压入产生式右部，最后记录步骤
            stack.pop();
            String productionStr = production.left + " -> " + production.right;

            // 将产生式右部逆序压栈（跳过ε）
            for (int i = production.right.size() - 1; i >= 0; i--) {
                String symbol = production.right.get(i);
                if (!symbol.equals("ε")) {
                    stack.push(symbol);
                }
            }
            // 记录应用产生式后的栈状态
            steps.add(new ParsingStep(stepNumber++, stack.toString(),
                    tokens.subList(index, tokens.size()).toString(), productionStr));
        }

        // 检查是否到达输入末尾
        if (index < tokens.size()) {
            // 剩余输入应该是从index到tokens.size()，包括结束符$
            List<String> remainingTokens = tokens.subList(index, tokens.size());
            String errorMessage = "错误: 解析完成但未到达输入末尾，剩余输入: " + remainingTokens;
            errorMessages.add(errorMessage);
            return false;
        }

        return !errorDetected;
    }

    /**
     * 恐慌模式错误恢复
     */
    private boolean recoverFromError(Stack<String> stack, String lookahead, int index, List<String> tokens) {
        String top = stack.peek();

        // 情况1: 栈顶是终结符，直接弹出
        if (grammar.terminals.contains(top)) {
            stack.pop();
            steps.add(new ParsingStep(steps.size() + 1, stack.toString(),
                    tokens.subList(index, tokens.size()).toString(),
                    "错误恢复: 弹出不匹配的终结符 " + top));
            return true;
        }

        // 情况2: 栈顶是非终结符
        Set<String> followSet = followSets.get(top);

        // 检查当前输入符号是否在栈顶非终结符的FOLLOW集中
        if (followSet.contains(lookahead)) {
            stack.pop(); // 弹出栈顶非终结符
            steps.add(new ParsingStep(steps.size() + 1, stack.toString(),
                    tokens.subList(index, tokens.size()).toString(),
                    "错误恢复: 弹出非终结符 " + top + "，因为 " + lookahead + " 在其FOLLOW集中"));
            return true;
        }

        // 情况3: 跳过输入符号直到找到同步符号
        Set<String> firstSet = firstSets.get(top);
        Set<String> syncSet = new HashSet<>(firstSet);
        syncSet.addAll(followSet);

        while (index < tokens.size() && !syncSet.contains(lookahead)) {
            index++;
            if (index < tokens.size()) {
                lookahead = tokens.get(index);
            }
        }

        if (index >= tokens.size()) {
            errorMessages.add("错误恢复失败: 找不到同步符号，到达输入末尾");
            return false;
        }

        steps.add(new ParsingStep(steps.size() + 1, stack.toString(),
                tokens.subList(index, tokens.size()).toString(),
                "错误恢复: 跳过输入符号直到找到同步符号 " + lookahead));

        return true;
    }
}
